package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 13:05
 * @description: 面试题 10.05. 稀疏数组搜索 <a href="https://leetcode.cn/problems/sparse-array-search-lcci/description/">...</a>
 **/
public class FindString {

	public int findString(String[] words, String s) {
		int left = 0, right = words.length;
		while (left < right) {
			while (left < right && words[left].isEmpty()) {
				left++;
			}
			while (left < right && words[right - 1].isEmpty()) {
				right--;
			}
			int mid = (left + right) >>> 1;
			while (mid < right && words[mid].isEmpty()) {
				mid++;
			}
			int cmp = words[mid].compareTo(s);
			if (cmp == 0) {
				return mid;
			} else if (cmp < 0) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		FindString findString = new FindString();
		System.out.println(findString.findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "ta"));
		System.out.println(findString.findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "car"));
		System.out.println(findString.findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "ball"));
	}
}
